package cn.leonis.leetcode;

/**
 * @author Tobi
 * @time 2021-07-10 1:24 PM
 * X的平方根,不允许使用库函数
 */
public class XSquareSolution {

    public static void main(String[] args) {
        XSquareSolution solution = new XSquareSolution();
        System.out.println(solution.mySqrt(2147395599));
        System.out.println(solution.testSqrt(2147395599));
        System.out.println(solution.testSqrt2(2147395599));
    }

    public int mySqrt(int x) {
        if (x < 2) {
            return x;
        }

        int left = 1, right = x;

        int mid = 0;

        while (left <= right) {
            mid = left + (right - left) / 2;
            if (x / mid == mid) {
                return mid;
            }else if (x / mid > mid) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return right;

    }

    public int testSqrt(int x) {
        return (int)Math.sqrt(x);
    }

    public int testSqrt2(int x) {
        int min = 1;
        int max = x;
        int pivot = 0;

        while (min <= max) {
            pivot = min + (max - min) / 2;
            long value = (long) pivot * pivot;

            if (value == x) {
                return pivot;
            } else if (x < value) {
                max = pivot - 1;
            } else {
                min = pivot + 1;
            }
        }

        return (long) pivot * pivot <= x ? pivot : pivot - 1;
    }
}
